/**
 * @author Todd
 */
package com.dudo.model;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;


public class Claim implements Comparable<Claim> {
	public static final int MAX_DICE = 10; // max dice in play
	public static final int[] combos = new int[MAX_DICE + 1];
	public static final int[][] choose = new int[MAX_DICE + 1][MAX_DICE + 1]; // n choose r
	public static final ArrayList<ArrayList<Claim>> diceClaims = new ArrayList<ArrayList<Claim>>(); // indexed by total dice, claim index
	public static final double[][][] claimProb = new double[MAX_DICE + 1][][]; // indexed by total dice, number in rank, rank; probability of claim holding a priori 
	
	static {
		// compute and store all numbers of combinations of dice
		combos[0] = 1;
		for (int n = 1; n < combos.length; n++)
			combos[n] = combos[n - 1] * 6;
		
		// compute and store n choose r
		for (int n = 1; n <= MAX_DICE; n++)
			choose[n][0] = 1;
		for (int n = 1; n <= MAX_DICE; n++)
			for (int r = 1; r <= n; r++)
				choose[n][r] = choose[n][r - 1] * (n - r + 1) / r;
		
		// Show n choose r values:
//		for (int n = 1; n <= MAX_DICE; n++) {
//			for (int r = 0; r <= n; r++) 
//				System.out.printf("%d\t", choose[n][r]);
//			System.out.println();
//		}

		// compute and store the probability of all claims a priori (i.e. without prior knowledge of rolls, etc.)
		for (int totalDice = 1; totalDice <= MAX_DICE; totalDice++) {
			claimProb[totalDice] = new double[totalDice + 1][7];
			for (int rank = 1; rank <= 6; rank++) {
				double probMatch = (rank == 1) ? (double)1 / 6 : (double)1 / 3;
				double probEvent = 1.0;
				for (int die = 1; die <= totalDice; die++)
					probEvent *= probMatch;
				for (int num = totalDice; num >= 1; num--) {
					claimProb[totalDice][num][rank] = choose[totalDice][num] * probEvent;
					if (num < totalDice)
						claimProb[totalDice][num][rank] += claimProb[totalDice][num + 1][rank]; // add probability of claim exceeded
					//System.out.printf("Probability that, out of %d dice, at least %d %d's were rolled = %g\n", totalDice, num, rank, claimProb[totalDice][num][rank]);
					probEvent *= (1 - probMatch) / probMatch;
				}
			}
		}

		// create indices of all valid claims for all numbers of dice.
		for (int totalDice = 0; totalDice <= MAX_DICE; totalDice++) {
			if (totalDice < 2)
				diceClaims.add(null);
			else {
				ArrayList<Claim> claims = new ArrayList<Claim>();
				for (int num = 1; num <= totalDice; num++)
					for (int rank = 1; rank <= 6; rank++)
						claims.add(new Claim(num, rank));
				claims.add(new Claim()); // default "dudo" claim
				Collections.sort(claims);
				diceClaims.add(claims);
			}
		}
	}
	
	public static double getRollProb(int totalDice, int num, int rank) {
		return claimProb[totalDice][num][rank];
	}
	
	public static double getRollProb(int totalDice, int num, int rank, int[] knownRolls) {
		int rollCount = 0;
		for (int roll : knownRolls)
			if (roll == 1 || roll == rank)
				rollCount++;
		int neededRolls = num - rollCount;
		if (neededRolls <= 0) return 1.0;
		int unknownRolls = totalDice - knownRolls.length;
		if (unknownRolls < neededRolls) return 0.0;
		return claimProb[unknownRolls][neededRolls][rank];
	}
	
	public static double getRollProb(int totalDice, Claim claim, int[] knownRolls) {
		return getRollProb(totalDice, claim.num, claim.rank, knownRolls);
	}
	
	public static void main(String[] args) {
		/*		
	    Dudo Statistics: In the bluffing dice game Dudo (a.k.a. Bluff, Perudo, Liar's Dice), players each simultaneously roll a 
	    number of standard D6 dice (six-sided, numbered 1-6) concealed underneath each player's dice cup.  Each player knows 
	    their own dice roll ranks (i.e. values), but other player dice roll ranks are unknown.  Players successively make 
	    ever-stronger claims until one player doubts the previous player's claim by saying "Dudo" (Spanish "I doubt").  1-rolls 
	    are wild in Dudo, so a roll of 1 may be counted as any rank.  Consider the following 10 dice roll: 1 1 2 3 3 4 5 5 5 6.  
	    With 1's wilde, this roll would support claims of less than or equal to two 1's, three 2's, four 3's, three 4's, five 
	    5's, and three 6's.  Detailed rules of Dudo are at http://cs.gettysburg.edu/~tneller/games/rules/dudo.pdf.

		It is helpful to know the probability that a given claim will be supported given a subset of known dice rolls.  
		
		Input (assumed valid integers):

		Total number of dice 
		Number of known values 
		Known values 
		
		Output:
		
		Prompts for information (as above) followed by a colon and a space. 
        A tab-separated table with probabilities for acheiving greater than or each positive count (1 through total number of 
        dice) for each rank (1 through 6). 
			tab-separated columns 
			probabilities to 3 decimal places (printf format "%.3f") 
			row for each rank (value) 1 through 6, beginning with the rank and a colon 
			columns for count 1 through the total number of dice 
			column headings: "Rank" above the ranks, "Count" and count numbers above the count columns (see below) 
		 */
		
		Scanner in = new Scanner(System.in);
		System.out.print("Total number of dice: ");
		int totalDice = in.nextInt(); 
		System.out.print("Number of known values: ");	
		int numKnown = in.nextInt();
		int[] diceRolled = new int[numKnown];
		if (numKnown > 0)
			System.out.print("Known values: ");
		for (int i = 0; i < numKnown; i++)
			diceRolled[i] = in.nextInt();
		System.out.print("\tCount\nRank");
		for (int num = 1; num <= totalDice; num++)
			System.out.printf("\t%d", num);
		System.out.println();
		for (int rank = 1; rank <= 6; rank++) {
			System.out.printf("%d:", rank);
			for (int count = 1; count <= totalDice; count++)
				System.out.printf("\t%.3f", getRollProb(totalDice, count, rank, diceRolled));
			System.out.println();
		}
	}
	
	
	private int num; // number of dice of a given rank claimed

	private int rank; // rank (dice pips) claimed

	public Claim() { // default constructor -> num == 0 -> dudo claim
	}

	public Claim(int num, int rank) { // "Do you think we collectively rolled <num> <rank>'s?"
		this.num = num;
		this.rank = rank;
	}
	
	@Override
	public int compareTo(Claim other) {
		if (num == 0) 
			return (other.num == 0) ? 0 : 1;
		if (other.num == 0)
			return -1;
		int compNum = (rank == 1) ? 2 * num : num;
		int compNumOther = (other.rank == 1) ? 2 * other.num : other.num;
		int compNumDiff = compNum - compNumOther;
		if (compNumDiff != 0)
			return compNumDiff;
		return rank - other.rank;
	}
	public boolean equals(Object other) {
		return compareTo((Claim) other) == 0;
	}

	public int getClaimIndex(int totalDice) {
		return diceClaims.get(totalDice).indexOf(this);
	}
	
	/**
	 * @return the number of dice claimed
	 */
	public int getNum() {
		return num;
	}

	/**
	 * @return the rank claimed
	 */
	public int getRank() {
		return rank;
	}

	public boolean isDudoClaim() {
		return num == 0;
	}
	
	public String toString() {
		if (num == 0)
			return "dudo";
		else
			return String.format("%d*%d", num, rank);
	}
}
